home *** CD-ROM | disk | FTP | other *** search
/ Cream of the Crop 25 / Cream of the Crop 25.iso / compress / tar321__.zip / SOURCES.ZIP / DEFLATE.C < prev    next >
C/C++ Source or Header  |  1996-07-03  |  30KB  |  804 lines
  1. /*
  2.  The following sorce code is derived from Info-Zip 'zip' 2.01
  3.  distribution copyrighted by Mark Adler, Richard B. Wales,
  4.  Jean-loup Gailly, Kai Uwe Rommel, Igor Mandrichenko and John Bush.
  5. */
  6.  
  7. #define window scope /* avoid TC warning */
  8.  
  9. /*
  10.  *  deflate.c is initially written by Jean-loup Gailly.
  11.  *
  12.  *  PURPOSE
  13.  *
  14.  *      Identify new text as repetitions of old text within a fixed-
  15.  *      length sliding window trailing behind the new text.
  16.  *
  17.  *  DISCUSSION
  18.  *
  19.  *      The "deflation" process depends on being able to identify portions
  20.  *      of the input text which are identical to earlier input (within a
  21.  *      sliding window trailing behind the input currently being processed).
  22.  *
  23.  *      The most straightforward technique turns out to be the fastest for
  24.  *      most input files: try all possible matches and select the longest.
  25.  *      The key feature of this algorithm is that insertions into the string
  26.  *      dictionary are very simple and thus fast, and deletions are avoided
  27.  *      completely. Insertions are performed at each input character, whereas
  28.  *      string matches are performed only when the previous match ends. So it
  29.  *      is preferable to spend more time in matches to allow very fast string
  30.  *      insertions and avoid deletions. The matching algorithm for small
  31.  *      strings is inspired from that of Rabin & Karp. A brute force approach
  32.  *      is used to find longer strings when a small match has been found.
  33.  *      A similar algorithm is used in comic (by Jan-Mark Wams) and freeze
  34.  *      (by Leonid Broukhis).
  35.  *         A previous version of this file used a more sophisticated algorithm
  36.  *      (by Fiala and Greene) which is guaranteed to run in linear amortized
  37.  *      time, but has a larger average cost, uses more memory and is patented.
  38.  *      However the F&G algorithm may be faster for some highly redundant
  39.  *      files if the parameter max_chain_length (described below) is too large.
  40.  *
  41.  *  ACKNOWLEDGEMENTS
  42.  *
  43.  *      The idea of lazy evaluation of matches is due to Jan-Mark Wams, and
  44.  *      I found it in 'freeze' written by Leonid Broukhis.
  45.  *      Thanks to many info-zippers for bug reports and testing.
  46.  *
  47.  *  REFERENCES
  48.  *
  49.  *      APPNOTE.TXT documentation file in PKZIP 1.93a distribution.
  50.  *
  51.  *      A description of the Rabin and Karp algorithm is given in the book
  52.  *         "Algorithms" by R. Sedgewick, Addison-Wesley, p252.
  53.  *
  54.  *      Fiala,E.R., and Greene,D.H.
  55.  *         Data Compression with Finite Windows, Comm.ACM, 32,4 (1989) 490-595
  56.  *
  57.  *  INTERFACE
  58.  *
  59.  *      int lm_init(void)
  60.  *          Initialize the "longest match" routines for a new file
  61.  *
  62.  *      int fast_deflate(char*, unsigned)
  63.  *      int lazy_deflate(char*, unsigned)
  64.  *          Processes a new input file and return its compressed length. Sets
  65.  *          the compressed length, crc, deflate flags and internal file
  66.  *          attributes.
  67.  */
  68.  
  69. #include <stdio.h>
  70. #include "modern.h"
  71. #include "zalloc.h"
  72. #include "zippipe.h"
  73. #include "zipdefs.h"
  74. #include "zipguts.h"
  75. #ifdef MODERN
  76. #  include <string.h>
  77. #else
  78. #  ifdef pyr /* Pyramid */
  79. #    define ZMEM /* No mem???() functions at all */
  80. #  endif
  81. #endif
  82.  
  83. /* Define this symbol if your target allows access to unaligned data.
  84.  * This is not mandatory, just a speed optimization. The compressed
  85.  * output is strictly identical.
  86.  */
  87. #ifndef UNALIGNED_OK
  88. #  ifdef MSDOS
  89. #   ifndef WIN32
  90. #    define UNALIGNED_OK
  91. #   endif
  92. #  endif
  93. #  ifdef i386
  94. #    define UNALIGNED_OK
  95. #  endif
  96. #  ifdef mc68020
  97. #    define UNALIGNED_OK
  98. #  endif
  99. #  ifdef vax
  100. #    define UNALIGNED_OK
  101. #  endif
  102. #endif
  103.  
  104. /* Compile with MEDIUM_MEM to reduce the memory requirements or
  105.  * with SMALL_MEM to use as little memory as possible. Use BIG_MEM if the
  106.  * entire input file can be held in memory (not possible on 16 bit systems).
  107.  * Warning: defining these symbols affects HASH_BITS (see below) and thus
  108.  * affects the compression ratio. The compressed output
  109.  * is still correct, and might even be smaller in some cases.
  110.  */
  111.  
  112. #ifdef SMALL_MEM
  113. #   define HASH_BITS  13  /* Number of bits used to hash strings */
  114. #endif
  115. #ifdef MEDIUM_MEM
  116. #   define HASH_BITS  14
  117. #endif
  118. #ifndef HASH_BITS
  119. #   define HASH_BITS  15
  120.    /* For portability to 16 bit machines, do not use values above 15. */
  121. #endif
  122.  
  123. #define HASH_SIZE (unsigned)(1<<HASH_BITS)
  124. #define HASH_MASK (HASH_SIZE-1)
  125. #define WMASK     (WSIZE-1)
  126. /* HASH_SIZE and WSIZE must be powers of two */
  127.  
  128. #define NIL 0
  129. /* Tail of hash chains */
  130.  
  131. #ifndef TOO_FAR
  132. #  define TOO_FAR 4096
  133. #endif
  134. /* Matches of length 3 are discarded if their distance exceeds TOO_FAR */
  135.  
  136. #ifdef ATARI_ST
  137. #  undef MSDOS /* avoid the processor specific parts */
  138.    /* (but the Atari should never define MSDOS anyway ...) */
  139. #endif
  140. #ifdef MSDOS
  141. #  ifndef NO_ASM
  142. #    ifndef ASMV
  143. #      define ASMV
  144. #    endif
  145. #  endif
  146. #endif
  147. #ifdef ASMV
  148. #  ifndef MSDOS
  149. #    ifdef DYN_ALLOC
  150.        #error: DYN_ALLOC not yet supported in match.s
  151. #    endif
  152. #  endif
  153. #endif
  154. #ifdef MSDOS
  155. #  ifndef __32BIT__
  156. #    define MAXSEG_64K
  157. #  endif
  158. #endif
  159.  
  160. /* Local data used by the "longest match" routines. */
  161.  
  162. #if defined(BIG_MEM) || defined(MMAP)
  163.   typedef unsigned Pos; /* must be at least 32 bits */
  164. #else
  165.   typedef ush Pos;
  166. #endif
  167. typedef unsigned IPos;
  168. /* A Pos is an index in the character window. We use short instead of int to
  169.  * save space in the various tables. IPos is used only for parameter passing.
  170.  */
  171.  
  172. #ifndef DYN_ALLOC
  173.   uch    window[2L*WSIZE];
  174.   /* Sliding window. Input bytes are read into the second half of the window,
  175.    * and move to the first half later to keep a dictionary of at least WSIZE
  176.    * bytes. With this organization, matches are limited to a distance of
  177.    * WSIZE-MAX_MATCH bytes, but this ensures that IO is always
  178.    * performed with a length multiple of the block size. Also, it limits
  179.    * the window size to 64K, which is quite useful on MSDOS.
  180.    * To do: limit the window size to WSIZE+BSZ if SMALL_MEM (the code would
  181.    * be less efficient since the data would have to be copied WSIZE/BSZ times)
  182.    */
  183.   Pos    prev[WSIZE];
  184.   /* Link to older string with same hash index. To limit the size of this
  185.    * array to 64K, this link is maintained only for the last 32K strings.
  186.    * An index in this array is thus a window index modulo 32K.
  187.    */
  188.   Pos    head[HASH_SIZE];
  189.   /* Heads of the hash chains or NIL. If your compiler thinks that
  190.    * HASH_SIZE is a dynamic value, recompile with -DDYN_ALLOC.
  191.    */
  192. #else
  193.    uch  far *window = NULL;
  194.    Pos  far *prev   = NULL;
  195.    Pos  far *head   = NULL;
  196. #endif
  197. #ifndef zalloc
  198.    void far *p_win  = NULL;
  199.    void far *p_prev = NULL;
  200.    void far *p_head = NULL;
  201. #else
  202. #  define p_win  window
  203. #  define p_prev prev
  204. #  define p_head head
  205. #endif
  206.  
  207. #define WINDOW_SIZE ((ulg)2*WSIZE)
  208.  
  209. long block_start;
  210. /* window position at the beginning of the current output block. Gets
  211.  * negative when the window is moved backwards. */
  212.  
  213. static unsigned ins_h;  /* hash index of string to be inserted */
  214. static char uptodate;   /* hash preparation flag */
  215.  
  216. #define H_SHIFT  ((HASH_BITS+MIN_MATCH-1)/MIN_MATCH)
  217. /* Number of bits by which ins_h and del_h must be shifted at each
  218.  * input step. It must be such that after MIN_MATCH steps, the oldest
  219.  * byte no longer takes part in the hash key, that is:
  220.  *   H_SHIFT * MIN_MATCH >= HASH_BITS */
  221.  
  222. unsigned int prev_length;
  223. /* Length of the best match at previous step. Matches not greater than this
  224.  * are discarded. This is used in the lazy match evaluation. */
  225.  
  226.        unsigned strstart;    /* start of string to insert */
  227.        unsigned match_start; /* start of matching string */
  228. static unsigned lookahead;   /* number of valid bytes ahead in window */
  229.        unsigned minlookahead;
  230.  
  231. unsigned max_chain_length;
  232. /* To speed up deflation, hash chains are never searched beyond this length.
  233.  * A higher limit improves compression ratio but degrades the speed. */
  234.  
  235. static unsigned int max_lazy_match;
  236. /* Attempt to find a better match only when the current match is strictly
  237.  * smaller than this value. This mechanism is used only for compression
  238.  * levels >= 4. */
  239.  
  240. #define max_insert_length  max_lazy_match
  241. /* Insert new strings in the hash table only if the match length
  242.  * is not greater than this length. This saves time but degrades compression.
  243.  * max_insert_length is used only for compression levels <= 3. */
  244.  
  245. unsigned good_match;
  246. /* Use a faster search when the previous match is longer than this */
  247.  
  248. /* Values for max_lazy_match, good_match and max_chain_length, depending on
  249.  * the desired pack level (0..9). The values given below have been tuned to
  250.  * exclude worst case performance for pathological files. Better values may
  251.  * be found for specific files. */
  252.  
  253. typedef struct config {
  254.    ush good_length; /* reduce lazy search above this match length */
  255.    ush max_lazy;    /* do not perform lazy search above this match length */
  256.    ush nice_length; /* quit search above this match length */
  257.    ush max_chain;
  258. } config;
  259.  
  260. #ifdef  FULL_SEARCH
  261. # define nice_match MAX_MATCH
  262. #else
  263.   int nice_match; /* Stop searching when current match exceeds this */
  264. #endif
  265.  
  266. static config configuration_table[10] = {
  267. /*      good lazy nice chain */
  268. /* 0 */ {0,    0,  0,    0},  /* store only */
  269. /* 1 */ {4,    4,  8,    4},  /* maximum speed, no lazy matches */
  270. /* 2 */ {4,    5, 16,    8},
  271. /* 3 */ {4,    6, 32,   32},
  272.  
  273. /* 4 */ {4,    4, 16,   16},  /* lazy matches */
  274. /* 5 */ {8,   16, 32,   32},
  275. /* 6 */ {8,   16, 128, 128},
  276. /* 7 */ {8,   32, 128, 256},
  277. /* 8 */ {32, 128, 258, 1024},
  278. /* 9 */ {32, 258, 258, 4096}}; /* maximum compression */
  279.  
  280. /* Note: the deflate() code requires max_lazy >= MIN_MATCH and max_chain >= 4
  281.  * For deflate_fast() (levels <= 3) good is ignored and lazy has a different
  282.  * meaning. */
  283.  
  284. /* Prototypes for local functions. */
  285. static unsigned fill_window OF((char*, unsigned));
  286. static void     init_hash   OF((void));
  287.  
  288. extern int longest_match OF((IPos cur_match));
  289. #ifdef ASMV
  290. extern int match_init OF((void)); /* asm code initialization */
  291. #endif
  292. #ifdef DEBUG
  293. static void check_match OF((IPos start, IPos match, int length));
  294. #endif
  295.  
  296. /* Update a hash value with the given input byte
  297.  * IN  assertion: all calls to to UPDATE_HASH are made with consecutive
  298.  *    input characters, so that a running hash key can be computed from the
  299.  *    previous key instead of complete recalculation each time. */
  300. #define UPDATE_HASH(h,c) (h = (((h)<<H_SHIFT) ^ (c)) & HASH_MASK)
  301.  
  302. /* Insert string s in the dictionary and set match_head to the previous head
  303.  * of the hash chain (the most recent string with same hash key). Return
  304.  * the previous length of the hash chain.
  305.  * IN  assertion: all calls to to INSERT_STRING are made with consecutive
  306.  *    input characters and the first MIN_MATCH bytes of s are valid
  307.  *    (except for the last MIN_MATCH-1 bytes of the input file). */
  308. #define INSERT_STRING(s, match_head) \
  309.    (UPDATE_HASH(ins_h, window[(s) + MIN_MATCH-1]), \
  310.     prev[(s) & WMASK] = match_head = head[ins_h], \
  311.     head[ins_h] = (s))
  312.  
  313. static void init_hash()
  314. {
  315.    register unsigned j;
  316.  
  317.    for (ins_h=0, j=0; j<MIN_MATCH-1; j++) UPDATE_HASH(ins_h, window[j]);
  318.    /* If lookahead < MIN_MATCH, ins_h is garbage, but this is
  319.       not important since only literal bytes will be emitted. */
  320. }
  321.  
  322. #ifdef DYN_ALLOC
  323. void lm_free() /* Free the window and hash table */
  324. {
  325.    if (p_win ) { zfree(p_win ); p_win  = NULL; }
  326.    if (p_prev) { zfree(p_prev); p_prev = NULL; }
  327.    if (p_head) { zfree(p_head); p_head = NULL; }
  328. }
  329.  
  330. int lm_alloc()
  331. {
  332.    if (!p_win) {
  333.       window = (uch*)zalloc(&p_win, WSIZE, 2*sizeof(uch));
  334.       if (!p_win) return ZNOMEM;
  335.    }
  336.    if (!p_prev) {
  337.       prev = (Pos*)zalloc(&p_prev, WSIZE,     sizeof(Pos));
  338.       if (!p_prev) { lm_free(); return ZNOMEM; }
  339.    }
  340.    if (!p_head) {
  341.       head = (Pos*)zalloc(&p_head, HASH_SIZE, sizeof(Pos));
  342.       if (!p_head) { lm_free(); return ZNOMEM; }
  343.    }
  344.    return 0;
  345. }
  346. #endif
  347.  
  348. /* A block of local deflate process data to be saved between
  349.  * sequential calls to deflate functions */
  350. static int match_available = 0; /* set if previous match exists */
  351. static unsigned match_length = MIN_MATCH-1; /* length of best match */
  352.  
  353. /* Initialize the "longest match" routines for a new file */
  354. int lm_init()
  355. {
  356. #ifdef ZMEM
  357.    register unsigned j;
  358. #endif
  359. #ifdef DYN_ALLOC
  360.    /* Use dynamic allocation if compiler dislike big static arrays: */
  361.    if (lm_alloc() != 0) return ZNOMEM;
  362. #endif
  363.    /* Initialize the hash table (avoiding 64K overflow for 16 bit systems).
  364.     * prev[] will be initialized on the fly. */
  365. #ifdef ZMEM
  366.    j = 0; do head[j] = NIL; while (++j < HASH_SIZE);
  367. #else
  368.    head[HASH_SIZE-1] = NIL;
  369.    memset((char*)head, NIL, (unsigned)(HASH_SIZE-1)*sizeof(*head));
  370. #endif
  371.    /* Set the default configuration parameters: */
  372.    max_lazy_match   = configuration_table[deflate_level].max_lazy;
  373.    good_match       = configuration_table[deflate_level].good_length;
  374. #ifndef FULL_SEARCH
  375.    nice_match       = configuration_table[deflate_level].nice_length;
  376. #endif
  377.    max_chain_length = configuration_table[deflate_level].max_chain;
  378.  
  379.    strstart = 0;
  380.    block_start = 0L;
  381. #ifdef ASMV
  382.    /* initialize the asm code */ if (match_init() != 0) return ZERROR;
  383. #endif
  384.    lookahead = 0;
  385.    uptodate  = 0;
  386.    minlookahead = MIN_LOOKAHEAD-1;
  387.    match_available = 0;
  388.    prev_length = MIN_MATCH-1;
  389.    return 0;
  390. }
  391.  
  392. /* Set match_start to the longest match starting at the given string and
  393.  * return its length. Matches shorter or equal to prev_length are discarded,
  394.  * in which case the result is equal to prev_length and match_start is
  395.  * garbage.
  396.  * IN assertions: cur_match is the head of the hash chain for the current
  397.  *   string (strstart) and its distance is <= MAX_DIST, and prev_length >= 1
  398.  */
  399. #ifndef ASMV
  400. /* For MSDOS, OS/2 and 386 Unix, an optimized version is in match.asm or
  401.  * match.s. The code is functionally equivalent, so you can use the C version
  402.  * if desired.  A 68000 version is in amiga/match_68.a -- this could be used
  403.  * with other 68000 based systems such as Macintosh with a little effort.
  404.  */
  405. int longest_match(cur_match)
  406.     IPos cur_match;                             /* current match */
  407. {
  408.    unsigned chain_length = max_chain_length;   /* max hash chain length */
  409.    register uch *scan = window + strstart;     /* current string */
  410.    register uch *match;                        /* matched string */
  411.    register int len;                           /* length of current match */
  412.    int best_len = prev_length;                 /* best match length so far */
  413.    IPos limit = strstart > (IPos)MAX_DIST ? strstart - (IPos)MAX_DIST : NIL;
  414.    /* Stop when cur_match becomes <= limit. To simplify the code,
  415.       we prevent matches with the string of window index 0. */
  416.  
  417. /* The code is optimized for HASH_BITS >= 8 and MAX_MATCH-2 multiple of 16.
  418.  * It is easy to get rid of this optimization if necessary. */
  419. #if HASH_BITS < 8 || MAX_MATCH != 258
  420.    #error Code too clever
  421. #endif
  422.  
  423. #ifdef UNALIGNED_OK
  424.    /* Compare two bytes at a time. Note: this is not always beneficial.
  425.       Try with and without -DUNALIGNED_OK to check. */
  426.    register uch *strend = window + strstart + MAX_MATCH - 1;
  427.    register ush scan_start = *(ush*)scan;
  428.    register ush scan_end   = *(ush*)(scan+best_len-1);
  429. #else
  430.    register uch *strend = window + strstart + MAX_MATCH;
  431.    register uch scan_end1 = scan[best_len-1];
  432.    register uch scan_end  = scan[best_len];
  433. #endif
  434.  
  435.    /* Do not waste too much time if we already have a good match: */
  436.    if (prev_length >= good_match) {
  437.        chain_length >>= 2;
  438.    }
  439.    Assert(strstart <= WINDOW_SIZE-MIN_LOOKAHEAD, "insufficient lookahead");
  440.  
  441.    do {
  442.        Assert(cur_match < strstart, "no future");
  443.        match = window + cur_match;
  444.  
  445.        /* Skip to next match if the match length cannot increase
  446.         * or if the match length is less than 2:
  447.         */
  448. #if (defined(UNALIGNED_OK) && MAX_MATCH == 258)
  449.        /* This code assumes sizeof(unsigned short) == 2. Do not use
  450.         * UNALIGNED_OK if your compiler uses a different size.
  451.         */
  452.        if (*(ush*)(match+best_len-1) != scan_end ||
  453.            *(ush*)match != scan_start) continue;
  454.  
  455.        /* It is not necessary to compare scan[2] and match[2] since they are
  456.         * always equal when the other bytes match, given that the hash keys
  457.         * are equal and that HASH_BITS >= 8. Compare 2 bytes at a time at
  458.         * strstart+3, +5, ... up to strstart+257. We check for insufficient
  459.         * lookahead only every 4th comparison; the 128th check will be made
  460.         * at strstart+257. If MAX_MATCH-2 is not a multiple of 8, it is
  461.         * necessary to put more guard bytes at the end of the window, or
  462.         * to check more often for insufficient lookahead.
  463.         */
  464.        scan++, match++;
  465.        do {
  466.        } while (*(ush*)(scan+=2) == *(ush*)(match+=2) &&
  467.                 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
  468.                 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
  469.                 *(ush*)(scan+=2) == *(ush*)(match+=2) &&
  470.                 scan < strend);
  471.        /* The funny "do {}" generates better code on most compilers */
  472.  
  473.        /* Here, scan <= window+strstart+257 */
  474.        Assert(scan <= window+(unsigned)(WINDOW_SIZE-1), "wild scan");
  475.        if (*scan == *match) scan++;
  476.  
  477.        len = (MAX_MATCH - 1) - (int)(strend-scan);
  478.        scan = strend - (MAX_MATCH-1);
  479.  
  480. #else /* UNALIGNED_OK */
  481.  
  482.        if (match[best_len]   != scan_end  ||
  483.            match[best_len-1] != scan_end1 ||
  484.            *match            != *scan     ||
  485.            *++match          != scan[1])      continue;
  486.  
  487.        /* The check at best_len-1 can be removed because it will be made
  488.         * again later. (This heuristic is not always a win.)
  489.         * It is not necessary to compare scan[2] and match[2] since they
  490.         * are always equal when the other bytes match, given that
  491.         * the hash keys are equal and that HASH_BITS >= 8.
  492.         */
  493.        scan += 2, match++;
  494.  
  495.        /* We check for insufficient lookahead only every 8th comparison;
  496.         * the 256th check will be made at strstart+258.
  497.         */
  498.        do {
  499.        } while (*++scan == *++match && *++scan == *++match &&
  500.                 *++scan == *++match && *++scan == *++match &&
  501.                 *++scan == *++match && *++scan == *++match &&
  502.                 *++scan == *++match && *++scan == *++match &&
  503.                 scan < strend);
  504.  
  505.        len = MAX_MATCH - (int)(strend - scan);
  506.        scan = strend - MAX_MATCH;
  507.  
  508. #endif /* UNALIGNED_OK */
  509.  
  510.        if (len > best_len) {
  511.            match_start = cur_match;
  512.            best_len = len;
  513.            if (len >= nice_match) break;
  514. #ifdef UNALIGNED_OK
  515.            scan_end = *(ush*)(scan+best_len-1);
  516. #else
  517.            scan_end1  = scan[best_len-1];
  518.            scan_end   = scan[best_len];
  519. #endif
  520.        }
  521.    } while ((cur_match = prev[cur_match & WMASK]) > limit
  522.             && --chain_length != 0);
  523.  
  524.    return best_len;
  525. }
  526. #endif /* ASMV */
  527.  
  528. #ifdef DEBUG
  529. /* Check that the match at match_start is indeed a match. */
  530. static void check_match(start, match, length)
  531. IPos start, match;
  532. int length;
  533. {
  534. #if ZMEM
  535.    register j;
  536.    for(j=0; j<length && window[match+j] == window[start+j]; j++);
  537.    if (j < length)
  538. #else
  539.    if (memcmp((char*)window + match, (char*)window + start, length) != 0)
  540. #endif
  541.    {
  542.       fprintf(stderr, " start %d, match %d, length %d\n",
  543.          start, match, length);
  544.       error("invalid match");
  545.    }
  546.    if (verbose > 1) {
  547.       fprintf(stderr,"\\[%d,%d]", start-match, length);
  548.       do { putc(window[start++], stderr); } while (--length != 0);
  549.    }
  550. }
  551. #else
  552. #  define check_match(start, match, length)
  553. #endif
  554.  
  555. /* Add a block of data into the window. Updates strstart and lookahead.
  556.  * IN assertion: lookahead < MIN_LOOKAHEAD.
  557.  * Note: call with either lookahead == 0 or length == 0 is valid
  558.  */
  559. static unsigned fill_window(buffer, length)
  560. char *buffer; unsigned length;
  561. {
  562.    register unsigned n, m;
  563.    unsigned more = length;
  564.  
  565.    /* Amount of free space at the end of the window. */
  566.    if (WINDOW_SIZE - lookahead - strstart < more) {
  567.       more = (unsigned)(WINDOW_SIZE - lookahead - strstart);
  568.    }
  569.    /* If the window is almost full and there is insufficient lookahead,
  570.     * move the upper half to the lower one to make room in the upper half.
  571.     */
  572.    if (strstart >= WSIZE+MAX_DIST) {
  573. #ifdef ZMEM
  574.       n = 0; do window[n] = window[n+WSIZE]; while (++n < WSIZE);
  575. #else
  576.       memcpy((char*)window, (char*)window+WSIZE, (unsigned)WSIZE);
  577. #endif
  578.       match_start -= WSIZE;
  579.       strstart    -= WSIZE; /* we now have strstart >= MAX_DIST: */
  580.  
  581.       block_start -= (long) WSIZE;
  582.  
  583.       for (n = 0; n < HASH_SIZE; n++) {
  584.          m = head[n];
  585.          head[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
  586.       }
  587.       for (n = 0; n < WSIZE; n++) {
  588.          m = prev[n];
  589.          prev[n] = (Pos)(m >= WSIZE ? m-WSIZE : NIL);
  590.          /* If n is not on any hash chain, prev[n] is garbage but
  591.             its value will never be used. */
  592.       }
  593.       if ((more += WSIZE) > length) more = length;
  594.    }
  595.    if (more) {
  596. #ifdef ZMEM
  597.       register char *p = (char*)window+strstart+lookahead;
  598.  
  599.       n = more; do *p++ = *buffer++; while (--n);
  600. #else
  601.       (void)memcpy((char*)window+strstart+lookahead, buffer, more);
  602. #endif
  603.       lookahead += more;
  604.    }
  605.    return more;
  606. }
  607.  
  608. /* Flush the current block, with given end-of-file flag.
  609.    IN assertion: strstart is set to the end of the current match. */
  610. #define FLUSH_BLOCK(eof) (void)flush_block(block_start >= 0L ?\
  611.         (char*)&window[(unsigned)block_start] : \
  612.         (char*)NULL, (long)strstart - block_start, (eof))
  613.  
  614. /* Processes a new input block.
  615.  * This function does not perform lazy evaluationof matches and inserts
  616.  * new strings in the dictionary only for unmatched strings or for short
  617.  * matches. It is used only for the fast compression options. */
  618. int fast_deflate(buffer, length)
  619. char *buffer; unsigned length;
  620. {
  621.    IPos hash_head; /* head of the hash chain */
  622.    int flush;      /* set if current block must be flushed */
  623.    unsigned accepted = 0;
  624.  
  625.    do {
  626.       /* Make sure that we always have enough lookahead, except
  627.        * at the end of the input file. We need MAX_MATCH bytes
  628.        * for the next match, plus MIN_MATCH bytes to insert the
  629.        * string following the next match. */
  630.       accepted += fill_window(buffer+accepted, length-accepted);
  631.       if (lookahead <= minlookahead) break;
  632.       if (!uptodate) {
  633.          match_length = 0; init_hash(); uptodate = 1;
  634.       }
  635.       while (lookahead > minlookahead) {
  636.          /* Insert the string window[strstart .. strstart+2] in the
  637.           * dictionary, and set hash_head to the head of the hash chain:
  638.           */
  639.          INSERT_STRING(strstart, hash_head);
  640.  
  641.          /* Find the longest match, discarding those <= prev_length.
  642.           * At this point we have always match_length < MIN_MATCH */
  643.          if (hash_head != NIL && strstart - hash_head <= MAX_DIST) {
  644.             /* To simplify the code, we prevent matches with the string
  645.              * of window index 0 (in particular we have to avoid a match
  646.              * of the string with itself at the start of the input file).
  647.              */
  648.             match_length = longest_match(hash_head);
  649.             /* longest_match() sets match_start */
  650.             if (match_length > lookahead) match_length = lookahead;
  651.          }
  652.          if (match_length >= MIN_MATCH) {
  653.             check_match(strstart, match_start, match_length);
  654.  
  655.             flush = ct_tally(strstart-match_start, match_length - MIN_MATCH);
  656.  
  657.             lookahead -= match_length;
  658.  
  659.             /* Insert new strings in the hash table only if the match length
  660.              * is not too large. This saves time but degrades compression.
  661.              */
  662.             if (match_length <= max_insert_length) {
  663.                 match_length--; /* string at strstart already in hash table */
  664.                 do {
  665.                     strstart++;
  666.                     INSERT_STRING(strstart, hash_head);
  667.                     /* strstart never exceeds WSIZE-MAX_MATCH, so there are
  668.                      * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
  669.                      * these bytes are garbage, but it does not matter since
  670.                      * the next lookahead bytes will be emitted as literals.
  671.                      */
  672.                 } while (--match_length != 0);
  673.                 strstart++;
  674.             } else {
  675.                 strstart += match_length;
  676.                 match_length = 0;
  677.                 ins_h = window[strstart];
  678.                 UPDATE_HASH(ins_h, window[strstart+1]);
  679. #if MIN_MATCH != 3
  680.                 Call UPDATE_HASH() MIN_MATCH-3 more times
  681. #endif
  682.             }
  683.          } else {
  684.             /* No match, output a literal byte */
  685.             Tracevv((stderr,"%c",window[strstart]));
  686.             flush = ct_tally (0, window[strstart]);
  687.             lookahead--;
  688.             strstart++;
  689.          }
  690.          if (flush) FLUSH_BLOCK(0), block_start = strstart;
  691.       }
  692.    } while (accepted < length);
  693.    if (!minlookahead) FLUSH_BLOCK(1); /* eof achieved */
  694.    return accepted;
  695. }
  696.  
  697. /* Same as above, but achieves better compression. We use a lazy
  698.  * evaluation for matches: a match is finally adopted only if there is
  699.  * no better match at the next window position.  */
  700. int lazy_deflate(buffer, length)
  701. char *buffer; unsigned length;
  702. {
  703.    IPos hash_head;          /* head of hash chain */
  704.    IPos prev_match;         /* previous match */
  705.    int flush;               /* set if current block must be flushed */
  706.    register unsigned ml = match_length; /* length of best match */
  707. #ifdef DEBUG
  708.    extern ulg isize;        /* byte length of input file, for debug only */
  709. #endif
  710.    unsigned accepted = 0;
  711.  
  712.    /* Process the input block. */
  713.    do {
  714.       /* Make sure that we always have enough lookahead, except
  715.        * at the end of the input file. We need MAX_MATCH bytes
  716.        * for the next match, plus MIN_MATCH bytes to insert the
  717.        * string following the next match. */
  718.       accepted += fill_window(buffer+accepted, length-accepted);
  719.       if (lookahead <= minlookahead) break;
  720.       if (!uptodate) {
  721.          ml = MIN_MATCH-1; /* length of best match */
  722.          init_hash();
  723.          uptodate = 1;
  724.       }
  725.       while (lookahead > minlookahead) {
  726.          INSERT_STRING(strstart, hash_head);
  727.  
  728.          /* Find the longest match, discarding those <= prev_length. */
  729.          prev_length = ml, prev_match = match_start;
  730.          ml = MIN_MATCH-1;
  731.  
  732.          if (hash_head != NIL && prev_length < max_lazy_match &&
  733.              strstart - hash_head <= MAX_DIST) {
  734.             /* To simplify the code, we prevent matches with the string
  735.              * of window index 0 (in particular we have to avoid a match
  736.              * of the string with itself at the start of the input file).
  737.              */
  738.             ml = longest_match (hash_head);
  739.             /* longest_match() sets match_start */
  740.             if (ml > lookahead) ml = lookahead;
  741.  
  742.             /* Ignore a length 3 match if it is too distant: */
  743.             if (ml == MIN_MATCH && strstart-match_start > TOO_FAR){
  744.                /* If prev_match is also MIN_MATCH, match_start is garbage
  745.                   but we will ignore the current match anyway. */
  746.                ml--;
  747.             }
  748.          }
  749.          /* If there was a match at the previous step and the current
  750.             match is not better, output the previous match: */
  751.          if (prev_length >= MIN_MATCH && ml <= prev_length) {
  752.  
  753.             check_match(strstart-1, prev_match, prev_length);
  754.  
  755.             flush = ct_tally(strstart-1-prev_match, prev_length - MIN_MATCH);
  756.  
  757.             /* Insert in hash table all strings up to the end of the match.
  758.              * strstart-1 and strstart are already inserted.
  759.              */
  760.             lookahead -= prev_length-1;
  761.             prev_length -= 2;
  762.             do {
  763.                strstart++;
  764.                INSERT_STRING(strstart, hash_head);
  765.                /* strstart never exceeds WSIZE-MAX_MATCH, so there are
  766.                 * always MIN_MATCH bytes ahead. If lookahead < MIN_MATCH
  767.                 * these bytes are garbage, but it does not matter since the
  768.                 * next lookahead bytes will always be emitted as literals.
  769.                 */
  770.             } while (--prev_length != 0);
  771.             match_available = 0;
  772.             ml = MIN_MATCH-1;
  773.             strstart++;
  774.             if (flush) FLUSH_BLOCK(0), block_start = strstart;
  775.  
  776.          } else if (match_available) {
  777.             /* If there was no match at the previous position, output a
  778.              * single literal. If there was a match but the current match
  779.              * is longer, truncate the previous match to a single literal.
  780.              */
  781.             Tracevv((stderr,"%c",window[strstart-1]));
  782.             if (ct_tally (0, window[strstart-1])) {
  783.                 FLUSH_BLOCK(0), block_start = strstart;
  784.             }
  785.             strstart++;
  786.             lookahead--;
  787.          } else {
  788.             /* There is no previous match to compare with,
  789.                wait for the next step to decide. */
  790.             match_available = 1;
  791.             strstart++;
  792.             lookahead--;
  793.          }
  794.          Assert(strstart <= isize && lookahead <= isize, "a bit too far");
  795.       }
  796.    } while (accepted < length);
  797.    if (!minlookahead) {/* eof achieved */
  798.       if (match_available) (void)ct_tally(0, window[strstart-1]);
  799.       (void)FLUSH_BLOCK(1); /* eof */
  800.    }
  801.    match_length = ml;
  802.    return accepted;
  803. }
  804.